﻿// 0821train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 小明有n个可选运动，每个运动有对应卡路里，想选出其中k个运动且卡路里和为t。
k，t，n都是给定的。求出可行解数量。

输入描述
第一行输入 n t k，用空格进行分割
第二行输入 每个运动的卡路里 按照空格进行分割

输出描述
求出可行解数量

输入
4 3 2
1 1 2 3
输出
2
说明
可行解为2，选取{0,2}, {1,2}两种方式。
 */

class Solution01
{
public:
    vector<vector<int>>result_vec;
    vector<int>track_vec;
    void backTrack(vector<int>&origin_vec, int start)
    {
        if (track_vec.size()>limit_)
        {
            return;
        }

        if (track_vec.size()==limit_)
        {
            int sum = 0;
            for (auto&num:track_vec)
            {
                sum += num;
            }
            if (sum==target_)
            {
                result_vec.push_back(track_vec);
            }
        }

	    for (int i=start; i<origin_vec.size();i++)
	    {
            track_vec.push_back(origin_vec[i]);
            backTrack(origin_vec, i + 1);
            track_vec.pop_back();
	    }
    }
    void solve01(vector<int>&origin_vec,int target, int limit)
    {
        //origin_vec里选出limit个运动，和为target
        limit_ = limit;
        target_ = target;

        backTrack(origin_vec, 0);

        cout << result_vec.size();
    }
private:
    int limit_, target_;
};


/*
 给出数字个数n和行数m (0 < n < 999，0 < m < 999)，从左上角的1开始，按照顺时针螺旋向内写方式，
 依次写出2, 3, ..., n，最终形成一个m行矩阵。 

小明对这个矩阵有些要求： 
1. 每行数字的个数一样多 
2. 列的数量尽可能少 
3. 填充数字时优先填充外部 
4. 数字不够时，使用单个*号占位

输入描述
两个整数，空格隔开，依次表示n、m

输出描述
符合要求的唯一短阵

输入
个数n 9和行数m 4
9 4

输出
1 2 3
* * 4
9 * 5
8 7 6
 */
class Solution02
{
public:
    bool is_complete = false;
    int row_start=0, row_end=0, col_start=0, col_end=0;
    void drawGrid(vector<vector<string>>&grid)
    {
        for (int c = col_start; c <= col_end; c++)
        {
            //填第一行
            if (curr_count > total_count_) break;
            grid[row_start][c] = to_string(curr_count);
            curr_count += 1;
        }
        if (curr_count > total_count_)
        {
            is_complete = true;
            return;
        }
        //------
           
    	for (int r = row_start+1; r <= row_end; r++)
    	{
            //填最后一列
            if (curr_count > total_count_) break;
    		grid[r][col_end] = to_string(curr_count);
    		curr_count += 1;
    	}
        if (curr_count > total_count_)
        {
            is_complete = true;
            return;
        }
        //------
            
    	//填最后一行
    	for (int c = col_end - 1; c >= col_start; c--)
    	{
            if (curr_count > total_count_) break;
    		grid[row_end][c] = to_string(curr_count);
    		curr_count += 1;
    	}
        if (curr_count > total_count_)
        {
            is_complete = true;
            return;
        }
        //------
          
    	//填第一列
    	for (int r = row_end - 1; r >= row_start + 1; r--)
    	{
            if (curr_count > total_count_) break;
    		grid[r][col_start] = to_string(curr_count);
    		curr_count += 1;
    	}
        

    }

    void solve02(int total_count, int row_size)
    {
        int col_size = ceil(static_cast<double>(total_count) / static_cast<double>(row_size));
        vector<vector<string>>grid(row_size, vector<string>(col_size, "*"));

        total_count_ = total_count;
        row_start = 0;
        row_end = row_size - 1;
        col_start = 0;
        col_end = col_size - 1;

        while (row_start<=row_end && col_start<=col_end && curr_count<=total_count)
        {
            drawGrid(grid);
            row_start += 1;
            row_end -= 1;
            col_start += 1;
            col_end -= 1;
        }

        for (auto&min_vec:grid)
        {
	        for (auto&num:min_vec)
	        {
                cout << num << ' ';
	        }
            cout << '\n';
        }

    }
private:
	int curr_count = 1;
	int total_count_ = 0;
};


/*
 停车场统计当日总收费，包月的车不统计，
 不包月的车半个小时收一块钱，不满半小时不收钱，
 如果超过半小时，零头不满半小时按半小时算，
 每天11:30-13:30时间段不收钱，如果一辆车停车时间超过8小时后不收费
 现提供停车场进出车辆的统计信息，需要你来计算停车场统计当日的总收费

输入描述：
第一行输入一个整数 n 表示今日进出停车场的包月的车辆数。
下一行输入包月车的车牌号，以空格分割。
接下来每行输出进出停车场的车辆信息。
进入停车场格式为：(时间 车牌号 enter)
离开停车场格式为：(时间 车牌号 leave)

输出描述：
输出今日总收费。

示例1：
输入：
2
AAA CCC
8:00 AAA enter
10:00 AAA leave
输出：
0

示例2：
输入：
1
AAA CCC
8:00 AAA enter
10:00 AAA leave
8:00 BBB enter
9:00 BBB leave
输出：
2
 */

//map存包月的车 //连续vector<vector<string>>
class Solution03
{
public:
    int free_start=11*60+30, free_end=13*60+30;
    int result = 0;
    unordered_set<string>free_set;
    int getTime(string&time_str)
    {
        int pos = time_str.find(":");
        int hour = stoi(time_str.substr(0, pos));
        int minute = stoi(time_str.substr(pos + 1));

        int count = hour * 60 + minute;
        return count;
    }

    int calculateCost(string&enter_time, string&leave_time)
    {
        /*
        不包月的车半个小时收 1，不满半小时不收钱，
		如果超过半小时，零头不满半小时按半小时算，
		每天11:30-13:30时间段不收钱，如果一辆车停车时间超过8小时后不收费
         */

        int enter_p = getTime(enter_time);
        int leave_p = getTime(leave_time);

        int totalDuration = leave_p - enter_p;

        //超过8小时免费
        if (totalDuration > 480) return 0;

        if (enter_p >= free_start && leave_p <= free_end) return 0;

        //小于30min免费
        if (totalDuration < 30) return 0;

        if (enter_p<free_start && leave_p>free_end)
        {
            int enter_part = free_start - enter_p;
            enter_part = max(30, enter_part);

            int leave_part = free_end - leave_p;
            leave_part = max(30, leave_part);

            return ceil(static_cast<double>(enter_part + leave_part) / 30);

        }

        if (enter_p >= free_start && enter_p <= free_end)
            enter_p = free_end;

        if (leave_p >= free_start && leave_p <= free_end)
            leave_p = free_start;

        return ceil(static_cast<double>(leave_p- enter_p) / 30);

    }


    void solve03(vector<string>&free_vec, vector<vector<string>>origin_vec)
    {
        for (auto&oh_str:free_vec)
        {
            free_set.insert(oh_str);
        }

        for (auto&item: origin_vec)
        {
            string name = item[0];
            //包月免费
            if (free_set.count(name) > 0) continue;
            string curr_enter = item[1];
            string curr_leave = item[2];
            int cost = calculateCost(curr_enter, curr_leave);
            result += cost;
        }
        cout << result;
    }
};

/*
考勤记录是分析和考核职工工作时间利用情况的原始依据，也是计算职工工资的原始依据。
为了正确地计算职工工资和监督工资基金使用情况，公司决定对员工的手机打卡记录进行异常排查。

异常判定规则
出现以下任意一种情况，即视为打卡异常：
1. 实际设备号与注册设备号不一致；
2. 同一个员工的两条打卡记录，时间间隔小于 60 分钟且打卡地点距离超过 5 km。

输入描述
第一行输入一个整数 N，表示打卡记录的条数。
后续 N 行，每行一条打卡记录，格式为：
工号,时间(分钟),打卡距离(km),实际设备号,注册设备号
（字段之间用英文逗号分隔）

输出描述
将所有异常打卡记录按输入顺序输出，记录之间用英文分号“;”分隔。
如果无异常记录，则输出字符串 null。

示例
示例1
输入
2
100000,10,1,ABCD,ABCD
100000,50,10,ABCD,ABCD

输出
100000,10,1,ABCD,ABCD;100000,50,10,ABCD,ABCD

示例2
输入
2
100000,10,1,ABCD,ABCD
100001,80,10,ABCE,ABCE

输出
null
 */
class Solution04
{
public:
};

int main()
{
	{
        //vector<string>free_vec;
        //vector<string>str_vec;

        //string free_count;
        //getline(cin, free_count);

        //string free_name;
        //getline(cin, free_name);
        //stringstream free_name_sstream(free_name);
        //string token;
        //while (free_name_sstream>>token)
        //{
        //    free_vec.push_back(token);
        //}
        //string input;
        //while (getline(cin,input))
        //{
        //    if (input.empty()) break;
        //    str_vec.push_back(input);
        //}

        vector<string>free_vec = {"AAA","CCC"};
        vector<string>str_vec = {"8:00 AAA enter","10:00 AAA leave","11:00 BBB enter","14:00 BBB leave"};

        vector<vector<string>>origin_vec;
        int index = 0;
        while (index<str_vec.size())
        {
            string enter_str = str_vec[index];
            string leave_str = str_vec[index + 1];

            vector<string>enter_vec;
            vector<string>leave_vec;

            string token;
            stringstream sstream_enter(enter_str);
            while (sstream_enter>>token)
            {
                enter_vec.push_back(token);
            }
            stringstream sstream_leave(leave_str);
            while (sstream_leave>>token)
            {
                leave_vec.push_back(token);
            }

            vector<string>curr_vec(3);
            //name enter leave
            curr_vec[0] = enter_vec[1];
            curr_vec[1] = enter_vec[0];
            curr_vec[2] = leave_vec[0];
            origin_vec.push_back(curr_vec);

            index += 2;
        }

        //11:00 14:00
        //string enter_time = "8:00";
        //string leave_time = "10:00";

        Solution03 solu;
        solu.solve03(free_vec, origin_vec);
        //cout << solu.calculateCost(enter_time, leave_time);

        return 0;
	}

	{
        //个数n 9和行数m 4
		//9 4
        //int total_count = 12, row_size = 4;
        int total_count, row_size;
        cin >> total_count >> row_size;
        Solution02 solu;
        solu.solve02(total_count, row_size);

        return 0;
	}


/*
4 3 2
1 1 2 3
n t k
k个运动且卡路里和为t

target=3, limit=2
 */
    //int target = 3, limit = 2;
    //vector<int>origin_vec = { 1,1,2,3 };
    int vec_size, target, limit;
    cin >> vec_size >> target >> limit;
    vector<int>origin_vec(vec_size);
    for (int i=0; i<vec_size; i++)
    {
        cin >> origin_vec[i];
    }

    Solution01 solu;
    solu.solve01(origin_vec,target, limit);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
